package com.zwxu.list;

public class SwapNodesInPairsDemo {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		ListNode node1 = new ListNode(1);
		ListNode node2 = new ListNode(2);
		ListNode node3 = new ListNode(3);
		ListNode node4 = new ListNode(4);
		node1.next = node2;
		node2.next = node3;
		node3.next = node4;
		//ListNode temp = node1;
		ListNode temp = swapPairs3(node1);
		while(temp != null){
			System.out.print(temp.val+">");
			temp = temp.next;
			
		}

	}
	
	public static ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
        while (head.next != null && head.next.next != null) {
            ListNode n1 = head.next;//要交换节点1
            ListNode n2 = head.next.next;//要交换节点2
            
            n1.next = n2.next;
            n2.next = n1;
            head.next = n2;
            // move to next pair
            head = n1;
        }

        return dummy.next;
    }
	
	/**
     * @param 递归
     * @return a ListNode
     */
	public static ListNode swapPairs3(ListNode head) {
        // Write your code here
        ListNode p = head;
        if(p==null || p.next==null)
            return p;
        
        ListNode pNextNext = p.next.next;//此顺序不能替换
        ListNode swapHead = p.next; // 交换p 和 p.next 两个结点
        swapHead.next = p; // 进行交换
        
        
        ListNode swapNextNext = swapPairs3(pNextNext); // 递归
        p.next = swapNextNext;
        return swapHead;
    }
	
	/**
     * @param 交换值
     * @return a ListNode
     */
    public ListNode swapPairs2(ListNode head) {
        // Write your code here
        ListNode p = head;
        if(p==null || p.next==null)
            return p;

        while(p != null && p.next != null){
            int val = p.val;
            p.val = p.next.val;
            p.next.val = val;
            p = p.next.next;
        }
        return head;

    }

}
class ListNode{
	int val;
	ListNode next;
	ListNode(int x){ val = x;}
}
